﻿// circular_queue.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>

using namespace std;


class MyCircularDeque1 {
public:
    struct ListNode {
        int val;
        ListNode* prev;
        ListNode* next;
        ListNode(int val) :val(val), prev(nullptr), next(nullptr) {};
    };

    ListNode* head;
    ListNode* tail;
    int curr_size;
    int max_size;

    MyCircularDeque1(int k) {
        curr_size = 0;
        max_size = k;

        head = new ListNode(0);
        tail = new ListNode(0);
        head->next = tail;
        tail->prev = head;
    }

    bool insertFront(int value) {
        if (isFull()) return false;
        ListNode* curr_head = head->next;
        ListNode* new_head = new ListNode(value);

        head->next = new_head;
        new_head->next = curr_head;
        new_head->prev = head;
        curr_head->prev = new_head;

        curr_size++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        ListNode* new_tail = new ListNode(value);
        ListNode* curr_tail = tail->prev;

        curr_tail->next = new_tail;
        new_tail->next = tail;
        new_tail->prev = curr_tail;
        tail->prev = new_tail;

        curr_size++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty())return false;
        ListNode* curr_head = head->next;
        ListNode* next = curr_head->next;

        head->next = next;
        next->prev = head;
        delete curr_head;

        curr_size--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty())return false;

        ListNode* curr_tail = tail->prev;
        ListNode* prev = curr_tail->prev;

        tail->prev = prev;
        prev->next = tail;
        delete curr_tail;

        curr_size--;
        return true;
    }

    int getFront() {
        if (isEmpty())return -1;
        return head->next->val;
    }

    int getRear() {
        if (isEmpty())return -1;
        return tail->prev->val;
    }

    bool isEmpty() {
        return curr_size == 0;
    }

    bool isFull() {
        return curr_size == max_size;
    }
};


class MyCircularDeque {
public:
    vector<int>my_vec;
    int max_size;

    MyCircularDeque(int k) {
        max_size = k;
    }

    int getSize()
    {
        return my_vec.size();
    }

    bool insertFront(int value) {
        int curr_size = getSize();
        if (curr_size + 1 > max_size) return false;

        vector<int>new_vec;
        new_vec.push_back(value);

        for (auto& item : my_vec)
        {
            new_vec.push_back(item);
        }
        my_vec = new_vec;

        return true;
    }

    bool insertLast(int value) {
        int curr_size = getSize();
        if (curr_size + 1 > max_size) return false;

        my_vec.push_back(value);
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        my_vec.erase(my_vec.begin());
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        my_vec.erase(my_vec.end()-1);
        return true;
    }

    int getFront() {
        //从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
        if (isEmpty()) return -1;
        return my_vec[0];
    }

    int getRear() {
        //获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
        if (isEmpty()) return -1;
        int curr_size = getSize();
        return my_vec[curr_size - 1];
    }

    bool isEmpty() {
        int curr_size = getSize();
        if (curr_size == 0) return true;
        return false;
    }

    bool isFull() {
        int curr_size = getSize();
        return max_size == curr_size;
    }
};


int main()
{
    MyCircularDeque1 circularDeque(3); // 设置容量大小为3
    cout << circularDeque.insertLast(1) << endl;			        // 返回 true
    cout << circularDeque.insertLast(2) << endl;			        // 返回 true
    cout << circularDeque.insertFront(3) << endl;			        // 返回 true
    cout << circularDeque.insertFront(4) << endl;			        // 已经满了，返回 false
    cout << circularDeque.getRear() << endl;  				// 返回 2
    cout << circularDeque.isFull() << endl;				        // 返回 true
    cout << circularDeque.deleteLast() << endl;			        // 返回 true
    cout << circularDeque.insertFront(4) << endl;			        // 返回 true
    cout << circularDeque.getFront() << endl;				// 返回 4

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
